//题目:
// 给你两棵二叉树： root1 和 root2 。
// 想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。
// 你需要将这两棵树合并成一棵新二叉树。合并的规则是：
// 如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
// 返回合并后的二叉树。

// 注意: 合并过程必须从两个树的根节点开始。
#include<iostream>
#include<queue>

using namespace std;
//代码:
struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution 
{
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) 
    {
        if(root1==nullptr)return root2;
        if(root2==nullptr)return root1;
        //以q1以主体，若q1中不存在q2的结点，则为它创建新节点
        queue<pair<unsigned int,TreeNode*>> q1,q2;
        q1.push(make_pair(1,root1)),q2.push(make_pair(1,root2));
        while(!q1.empty() && !q2.empty())
        {
            pair<unsigned int,TreeNode*> pir1=q1.front(), pir2=q2.front();
            if(pir1.first==pir2.first && pir1.second!=nullptr && pir2.second!=nullptr)
            {
                //出队列
                q1.pop(),q2.pop();
                TreeNode* node1=pir1.second,*node2=pir2.second;
                //1.对应结点值相加
                node1->val+=node2->val;
                //2.弥补1树对应结点不存在，而2树对应结点存在的情况
                if(node1->left==nullptr && node2->left!=nullptr)
                {
                    node1->left=new TreeNode(node2->left->val);
                    node2->left->val=0;
                }
                if(node1->right==nullptr && node2->right!=nullptr)
                {
                    node1->right=new TreeNode(node2->right->val);
                    node2->right->val=0;
                }
                //3.子节点入队列
                if(node1->left)q1.push(make_pair(pir1.first*2,node1->left));
                if(node1->right)q1.push(make_pair(pir1.first*2+1,node1->right));
                if(node2->left)q2.push(make_pair(pir2.first*2,node2->left));
                if(node2->right)q2.push(make_pair(pir2.first*2+1,node2->right));
            }
            //如果出现pir1.first！=pir2.first的情况，那一定是1树对应结点存在，而2树对应结点不存在,让1树节点出队列即可
            else q1.pop();
        }
        return root1;
    }   
};